Approach and Coverage

Methodology#

The code samples in this course are written in the Python programming language. However, to make the course accessible to readers not familiar with all of Python’s constructs and keywords, the code samples have been simplified. For example, a reader won’t find any of the keywords public, protected, private, or static. A learner also won’t find much discussion about class hierarchies. Which interfaces a particular class implements or which class it extends, if relevant to the discussion, should be clear from the accompanying text.

These conventions should make the code samples understandable by anyone with a background in any of the languages from the ALGOL tradition, including B, C, C++, C#, Objective-C, D, Python, JavaScript, and so on. Readers who want the full details of all implementations are encouraged to look at the Python source code that accompanies this course.

This course mixes mathematical analyses of running times with Python source code for the algorithms being analyzed. This means that some equations contain variables also found in the source code. These variables are typeset consistently, both within the source code and within equations. The most common such variable is the variable $n$ that, without exception, always refers to the number of items currently stored in the data structure.

List of data structures#

The below tables summarize the performance of data structures in this course that implement each of the interfaces, List, USet, and SSet, described before.

• $^A$ Denotes an amortized running time.

• $^E$ Denotes an expected running time.

In the table shown below, BinaryTrie, XFastTrie, and YFastTrie is the structure that can only store $w$-bit integer data.

BTree denotes the running time in the external-memory model.

• $^{\text{I}}$ This structure can only store $w$-bit integer data.
• $^{\text{X}}$ This denotes the running time in the external-memory model.

Module relationships#

The following illustration shows the dependencies between various modules in this course. A solid arrow shows a strong dependency of a module on the other one. A dashed arrow indicates only a weak dependency, in which only a small part of the module depends on another module or only the main results of the other module.